package com.fallsvc.dayproblem.demo202511;

import java.util.*;

/**
 * @auther falls_vc
 * description:
 * @date 2025/11/8  15:24
 */
public class Demo20251108 {
//    https://leetcode.cn/problems/M1oyTv/description/
    public static void main(String[] args) {
        StringBuilder stringBuilder = new StringBuilder();
        Map<String,Integer> map = new HashMap<>();
//        stringBuilder.deleteCharAt(0);

//        System.out.println(minWindow("ADOBECODEBANC", "ABC"));
    }

    // 自己写的没有通过
//    public static String minWindow(String ss, String tt) {
//        char[] s = ss.toCharArray();
//        char[] t = tt.toCharArray();
//        Map<Character,Integer> need = new HashMap<>(); // 存需要字符
//        Map<Character,Integer> map = new HashMap<>(); // 存当前字符和个数
//
//        for(char ch : t) {
//            need.put(ch,need.getOrDefault(ch,0)+1);
//        }
//
//        int left=0;
//        int right=-1;
//        int rl=-1;
//        int rr=-1;
//        int count = 0;// 有效
//
//        for(char ch : s) {
//            right++;
//
//            if(need.containsKey(ch)) {
//                map.put(ch,map.getOrDefault(ch,0) + 1);
//                if(need.get(ch) == map.get(ch)) {
//                    count++;
//                }
//            }
//
//
//            while(count == need.size()) {
//
//                if(rr == -1 || right-left < rr-rl ) {
//                    rl = left;
//                    rr = right;
//                }
//
//
//                char f= s[left];
//                if(map.containsKey(f)) {
//                    int n =map.get(f)-1;
//                    if(n == 0) {
//                        map.remove(f);
//                    }else {
//                        map.put(f,n);
//                    }
//
//                    if(need.get(f) == n + 1)
//                        count--;
//                }
//
//                left++;
//            }
//        }
//        return rl == -1 && rr == -1 ? "" : ss.substring(rl,rr+1);
//    }

    class Solution {
        Map<Character, Integer> ori = new HashMap<Character, Integer>();
        Map<Character, Integer> cnt = new HashMap<Character, Integer>();

        public String minWindow(String s, String t) {
            // 需要元素放入ori
            int tLen = t.length();
            for (int i = 0; i < tLen; i++) {
                char c = t.charAt(i);
                ori.put(c, ori.getOrDefault(c, 0) + 1);
            }
            int l = 0, r = -1;
            int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
            int sLen = s.length();
            while (r < sLen) {
                ++r;
                if (r < sLen && ori.containsKey(s.charAt(r))) {
                    cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
                }
                while (check() && l <= r) {
                    if (r - l + 1 < len) {
                        len = r - l + 1;
                        ansL = l;
                        ansR = l + len;
                    }
                    if (ori.containsKey(s.charAt(l))) {
                        cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
                    }
                    ++l;
                }
            }
            return ansL == -1 ? "" : s.substring(ansL, ansR);
        }

        public boolean check() {
            Iterator iter = ori.entrySet().iterator();
            while (iter.hasNext()) {
                Map.Entry entry = (Map.Entry) iter.next();
                Character key = (Character) entry.getKey();
                Integer val = (Integer) entry.getValue();
                if (cnt.getOrDefault(key, 0) < val) {
                    return false;
                }
            }
            return true;
        }
    }

//    作者：力扣官方题解
//    链接：https://leetcode.cn/problems/M1oyTv/solutions/1417786/han-you-suo-you-zi-fu-de-zui-duan-zi-fu-a8q50/
//    来源：力扣（LeetCode）
//    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
}
